Software tampering is an attack which has the purpose of altering the way a piece of software operates in such a way that it brings illegitimate benefits to the attacker. The objectives of tampering could be to circumvent/disable copy protection or security mechanisms, to extract secret or copyrighted material, or to introduce malicious code such as computer viruses.
In many situations, the illegitimate benefits may involve substantial financial disadvantages for software producers. Consequently, both attackers and software vendors may be expected to make significant efforts to break and improve protection mechanisms against software tampering, respectively. In the context of mobile phones, protection of the SIM-lock and other sensitive software components, e.g. Digital Rights Management (DRM), are of particular interest. Furthermore, tamper protection of other software entities and/or for other purposes and/or in connection with other uses may also be beneficial.
In order to modify a software component, an attacker typically has to acquire at least a partial understanding of how the software component functions. Software tampering may thus be delayed if not prevented by making reverse engineering more difficult. Transformations, which make the software harder to analyze are useful to this end; such transformations are generally referred to as obfuscation.
Techniques for reverse engineering software may roughly be divided in two groups of techniques: Static (or “offline”) code analysis and dynamic (or “live”) code analysis. When performing dynamic analysis, the software is observed as it is executing. In contrast, static analysis is usually limited to an examination/analysis of some representation of the program code, without actually executing it. One technique employed in dynamic analysis is the comparison of execution traces.
An execution trace of a program typically includes the sequence of memory addresses from which the executable instructions are read during execution of a program. Execution traces may thus be collected by running the program, e.g. by using specific hardware support (so-called trace buffers) or by a software-based recording of the addresses. Using an execution trace and the executable code of the program, the actual sequence of executed instructions can thus be recreated.
By providing two sets of stimuli and comparing the differences in the resulting execution traces, an attacker can gain knowledge of the software component. In particular, comparison of execution traces may identify critical decision points of the program. In the context of the SIM-lock and DRM-solutions of mobile devices, tests for correct signatures or checksums are examples of critical decision points. For example, an attacker may compare the execution traces of the software run by two different mobile devices, e.g. an operator-locked device and a device that is not operator-locked, so as to obtain information about which parts of the program are relevant for the SIM-lock functionality.
Previous attempts to make reverse engineering by dynamic analysis more difficult include attempts to limit the opportunities for an attacker to observe the program as it is executing. However, such counter-measures have generally been specific to a particular platform and/or a specific reverse-engineering tool, such as a specific debugger.
One example of such counter-measures includes encrypting the executable code and the use of specific hardware that combines decryption and execution of the code. Even though properly implemented hardware-based decryption techniques can offer good protection, this protection is achieved at the price of additional, specific hardware.
Another approach, known as anti-debugger techniques, has the purpose of complicating the process of observing the program execution in a particular debugger. On some platforms, the executing code can query the operating systems for a possible debugger that is attached to the process and e.g. terminate if this is the case. Another option is to interfere with the techniques used by the debugger, for instance by tampering with the setting of break points. However, anti-debugger techniques are specific to a particular debugger and do not provide a general purpose tamper protection technique. Furthermore, instruction-set simulators and hardware-supported debuggers are commonly used when debugging embedded systems, thus reducing the practical usefulness of anti-debugger techniques. Furthermore, execution traces may still be collected using trace buffers that are entirely implemented in hardware.
Obfuscation is a technique used to complicate code. Obfuscation makes code harder to understand when it is de-compiled, but it typically has no effect on the functionality of the code. Obfuscation of programs can be used to protect programs by making them harder to reverse-engineer.
A number of obfuscation techniques have been proposed. The article “Program Obfuscation Scheme Using Random Numbers to complicate Control Flow” by Tatsuya Toyofuku et al, in T Enokido et al. (Eds.): EUC Workshops 2005. LNCS 3823, pp. 916-925, 2005, proposes one such obfuscation scheme. However, this method was reported to be vulnerable to dynamic analysis.
WO 01/69355 discloses a method for embedding a watermark into a computer-program by inserting additional routines in the program along with a number of randomly established additional control flows, thus resulting in a particular, i.e. the watermarked, version of the program having a corresponding control flow.
U.S. Pat. No. 6,668,325 and the article “Watermarking, Tamper-proofing, and Obfuscation—Tools for Software protection” by Christian S. Collberg and Clark Thomborson, IEEE Transactions on Software engineering, 28:6 (June 2002), describe a number of obfuscating transformations. On such transformation introduces redundant if-statements. The condition of the if-statement is a so-called opaque predicate which has some property that is known when the program is obfuscated but difficult to identify by static analysis of the code. Opaque predicates that always evaluate to e.g. TRUE may be used in such an if-statement. Consequently, at obfuscation time it is known that only one of the branches of the if-statement will be executed. Thus, during obfuscation the code to be executed may be inserted into that branch, while the other branch that is never executed may include some arbitrary “dummy” code. The above prior art document further describes the use of opaque predicates whose outcome may be either TRUE or FALSE for the selection of one of two alternative instances of a given computational task. However, even though this technique makes the static analysis of the code harder, it does not efficiently increase the difficulty of a dynamic analysis attempting to identify critical decision points.
One particular transformation disclosed in U.S. Pat. No. 6,668,325 is referred to as an ordering transformation and involves a randomized placement of source code items (terms within expressions, statements within basic blocks, etc.), so as to prevent reverse-engineering of the code. The reordering of the source code items is performed based on a dependency analysis which is performed to determine which re-orderings are technically valid. Hence, this prior art transformation process generates one of the technical possible re-orderings of the source code to be implemented. Consequently the resulting executable code will represent this generated ordering.
However, it remains a general problem to provide efficient methods of obfuscating program code so as to make it more difficult to gain useful information from an analysis of the execution trace of the program, e.g. in order to identify interesting decision points and/or other critical points.